import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-17
 * Time: 22:42
 */
class Solution {
//     回溯
//     转化为 往 2*n 个位置上填括号
//     注意 右括号匹配完了, 就只能用左括号
//     左括号用完了, 就只能用右括号
//     其他情况, 先左括号, 后右括号
    public List<String> list=new ArrayList<>();
    public char[] arr;
    public void dfs(int index, int n, int left, int right){
        if(index==arr.length){
            list.add(new String(arr));
            return;
        }
        // 只能填左括号的情况, 就是(已经用的)右括号 匹配完了
        if(left==right){
            this.arr[index]='(';
            dfs(index+1, n, left+1, right);
            return;
        }
        if(left==n){
            // 只能填右括号的情况, 就是左括号用完了
            this.arr[index]=')';
            dfs(index+1, n, left, right+1);
            return;
        }
        // 两种括号都能用的情况
        // 先填左括号
        this.arr[index]='(';
        dfs(index+1, n, left+1, right);
        // 再填右括号
        this.arr[index]=')';
        dfs(index+1, n, left, right+1);
    }
    public List<String> generateParenthesis(int n) {
        this.arr=new char[2*n];
        dfs(0, n, 0, 0);
        return list;
    }
}
